'''
https://leetcode.cn/problems/find-k-th-smallest-pair-distance/description/
'''
from typing import List


class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        n = len(nums)
        def count(dis):
            # 返回 有序数组nums 中一对数的差值 <= dis 的对数
            # 滑动窗口
            l, r = 0, 0
            ans = 0
            while l < n:
                while r < n and nums[r] - nums[l] <= dis:
                    r += 1
                ans += r - l - 1    # l,r 是正确的位置，以l为起点的数值对
                l += 1
            return ans

        nums.sort()
        l, r = 0, nums[-1] - nums[0]
        ans = 0
        while l <= r:
            dis = (l + r) // 2
            if count(dis) < k:
                l = dis + 1
            else:
                r = dis - 1
                ans = dis
        return ans

nums = [1, 6, 1]
k = 3
print(Solution().smallestDistancePair(nums, k))

